\documentclass[10pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
% Interactive index
\usepackage{hyperref}
% Spanish titles
\usepackage[spanish]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
% Code listings
\usepackage{listings}
\lstset{
 language=Oz,
 numbers=left,
 numberstyle=\footnotesize,
 stepnumber=0,
%
 tabsize=2,
 breaklines=true,
 breakatwhitespace=false,
 showstringspaces=false,
 showtabs=false,
%
 frame=none
%
 escapeinside={\% ~ ;}
}

\date{\today}
\begin{document}
% \newpage
% \listoffigures
% \listoftables
\section{Procesamiento de Listas}

Las listas juegan un papel importante en Lisp por razones históricas y prácticas. Historicamente, las listas eran el tipo compuesto original de Lisp. Actualmente un programador de Common Lisp en muchos casos probablemente use un vector, un hash-table o algún tipo definido por el usuario en vez de usar una lista.

\subsection{¡No existen las listas!}
La clave para entender las listas es entender que son realmente una ilusión construida sobre objetos que son instancias de un tipo de datos más primitivo.

\textbf{CONS} (de "construct", construcción) toma dos argumentos y retorna una nueva celda cons conteniendo los dos valores. Estos valores pueden ser referencias a cualquier tipo de objeto. A menos que el segundo valor sea \textbf{NIL} u otra celda cons, un cons es impreso como los dos valores entre paréntesis separados por un punto, que se nombran dotted-pair.

\begin{lstlisting}
(cons 1 2)                        ; (1 . 2)
\end{lstlisting}

Los dos valores en una celda cons son llamados el \textbf{CAR} y el \textbf{CDR} de una celda, debido a las instrucciones de la computadora con la que se accedían (Contents of Address part of Register number, Contents of Decrement part of Register number):

\begin{lstlisting}
(car (cons 1 2))                  ; 1
(cdr (cons 1 2))                  ; 2
\end{lstlisting}

Ambos (\textbf{CAR} y \textbf{CDR}) son también luagares que puede ser seteados por \textbf{SETF}; dada una celda cons existente, es posible asignar un nuevo valor a cualquiera de sus valores.

\begin{lstlisting}
(defparameter *cons* (cons 1 2))
*cons*                            ; (1 . 2)
(setf (car *cons*) 10)            ; (10 . 2)
(setf (cdr *cons*) 20)            ; 20
*cons*                            ; (10 . 20)

\end{lstlisting}

Como los valores en una celda cons pueden ser referencias a cualquier tipo de objeto, se puede construir estructuras mas grandes linkeando celdas cons entre si. Las listas están construidas de esta forma, linkeando celdas cons en una cadena. Los elementos de la lista estan guardados en el \textbf{CAR} de la celda mientras que en \textbf{CDR} contiene la referencia a la siguiente celda cons. La última celda en la cadena tiene un \textbf{NIL} como valor en su \textbf{CDR}.

Entonces cuando se dice que un valor en particular es una lista, lo que realmente se esta diciendo es que el valor es \textbf{NIL} o es una referencia a una celda cons. El car de la celda es el primer elemento de la lista, y el CDR es una referencia a otra lista, que es, otra celda cons o \textbf{NIL}, conteniendo los elementos restantes. El printer de Lisp entiende esta convención y imprime las cadenas de celdas cons como listas entre paréntesis en vez de sus dotted-pairs.un par de puntos llamados.

\begin{lstlisting}
(cons 1 nil)                      ; (1)
(cons 1 (cons 2 nil))             ; (1 2)
(cons 1 (cons 2 (cons 3 nil)))    ; (1 2 3)
\end{lstlisting}
%\newpage
%Cuando hablamos sobre estructuras construidas sobre celdas, algunos diagramas pueden ser de gran ayuda.

%\begin{figure}[htb]
%  \includegraphics[width=0.4\textwidth]{celda}
%  \label{fig:celda}
%\end{figure}

%La caja a la izquierda representa el CAR, y la caja de la derecha representa el CDR. Por ejemplo, la lista (A B C), que consiste de tres %celdas cons linkeadas por sus CDRs, se diagramaría de esta forma:

%\begin{figure}[htb]
%  \includegraphics[width=0.4\textwidth]{ejemploCelda}
%  \label{fig:celda}
%\end{figure}


\end{document}